import java.util.*;

/**
 * @Author 12629
 * @Description： STL
 */
class Student {

}
class ImpLess implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o1.compareTo(o2);
    }
}

class ImpBig implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}

public class Test {

    /**
     * 不算是topk的真正的解法
     * @param array
     * @param k
     * @return
     */
    public static int[] topk1(int[] array,int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        //O(n*logN)
        for (int i = 0; i < array.length; i++) {
            queue.offer(array[i]);
        }
        //O(k*logN)
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }
        return ret;
    }

    //k*logK + (N-K)*logK = O(N*logK)
    public static int[] topK(int[] array,int k) {

        int[] ret = new int[k];
        if(k <= 0) {
            return ret;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(k,new ImpBig());
        //O(k*logK)
        for (int i = 0; i < k; i++) {
            queue.offer(array[i]);
        }
        //从第K+1个元素开始进行遍历 O((N-K)*logK)
        for (int i = k; i < array.length; i++) {
            //先获取堆顶元素
            int val = queue.peek();
            if(val > array[i]) {
                queue.poll();
                queue.offer(array[i]);
            }
        }
        //走到这里队列里面就是前K个最小的元素
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }
        return ret;
    }

    public static void main5(String[] args) {
        int[] array = {1,12,3,41,5,16,7,81,9,10};
        int[] ret = topK(array, 3);
        System.out.println(Arrays.toString(ret));


        PriorityQueue<Integer> queue = new PriorityQueue<>( new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2.compareTo(o1);
                }
            }
        );

    }



    public static void main4(String[] args) {

        PriorityQueue<Integer> queue = new PriorityQueue<>(new ImpBig());

        queue.offer(10);
        queue.offer(5);

        System.out.println(queue.peek());
        queue.poll();
    }


    public static void main3(String[] args) {
        PriorityQueue<Student> queue = new PriorityQueue<>();

        PriorityQueue<Student> queue2 = new PriorityQueue<>(15);

        ArrayList<Integer>list = new ArrayList<>();
        list.add(1);
        list.add(10);
        list.add(5);

        PriorityQueue<Integer> queue3 = new PriorityQueue<>(list);
        System.out.println("===");

        /*LinkedList<Student> queue1 = new LinkedList<>();
        queue1.offer(null);
        queue1.offer(null);
        System.out.println(queue1.size());*/
    }

    public static void main2(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(10);
        queue.offer(2);
        queue.offer(5);

        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());

    }

    public static void main(String[] args) {
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        TestHeap testHeap = new TestHeap();
        testHeap.init(array);

        testHeap.createHeap();


        //testHeap.offer(80);
        //testHeap.poll();

        testHeap.heapSort();
        System.out.println("=====");

        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);

    }
}
